package eazy.ListNode;

import utils.ListNode;

import java.util.List;

public class hasCycle_141 {


    public static void main(String[] args) {
        ListNode listNode1 = new ListNode();
        ListNode listNode2 = new ListNode();
        ListNode l1 = new ListNode();
        listNode1.val = 6;
        listNode2.val = 2;

        l1.next=listNode1;
        listNode1.next=listNode2;
        hasCycle_141 hasCycle_141 = new hasCycle_141();
        boolean b = hasCycle_141.hasCycle(l1);
        System.out.println(b);
    }
    public boolean hasCycle(ListNode head){
        if (head==null||head.next==null){
            return  false;
        }
        ListNode slow =head;
        ListNode fast =head.next;
        while (slow!=fast){
            if (fast==null||fast.next==null){
                return false;
            }
            slow=slow.next;
            fast=fast.next.next;
        }
        return true;
    }
//    时间复杂度：O(N)，其中 NN 是链表中的节点数。
//    当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次。
//    当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动 N 轮。

//    空间复杂度：O(1)。我们只使用了两个指针的额外空间。
}
